/**
 * Implement strStr()
Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, 
or null if needle is not part of haystack.
 */
package com.xinpan.exercise;

public class StrStr {
    public String strStr(String haystack, String needle) 
    {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(haystack == null || needle == null || needle.length() > haystack.length())
            return null;
        
        int i = 0;
        int j = 0;
        while(i < haystack.length() - needle.length() + 1)
        {
            while(j < needle.length() && haystack.charAt(i) == needle.charAt(j))
            {
                i++;
                j++;
            }
            if(j == needle.length())
                return haystack.substring(i-j, haystack.length());
            i = i - j + 1;
            j = 0;
        }
        return null;
    }
}
